This specification relates to database query optimization. Query optimizers are used by database management systems to determine or identify efficient plans for executing queries. Estimating the cost for executing a query plan typically includes determining an expected number of input/output operations and an estimate of the processing time required to perform the plan. Query optimizers can represent queries to be optimized, such as an Structured Query Language (SQL) queries, as join graphs where tables in SQL FROM clauses are represented as vertices in the join graph. Join predicates between tables are represented as edges between vertices in the join graph.